import java.util.Arrays;

public class PriorityQueue {
    public int[] elem;
    public int usedSize;

    public PriorityQueue() {

    }
    public void createHeap(int[] array) {
        this.elem= Arrays.copyOf(array,array.length);
        this.usedSize=array.length;
        int root=(usedSize-2)/2;
        for(;root>=0;root--){
            shiftDown(root,usedSize);
        }

    }

    private void shiftDown(int root,int len) {
        int parent=root;
        int child=root*2+1;
        while(child<len){
            if(child+1<len && elem[child+1]>elem[child]){
                child=child+1;
            }
            if(elem[parent]<elem[child]){
                int tmp=elem[parent];
                elem[parent]=elem[child];
                elem[child]=tmp;
            }else{
                break;
            }
            parent=child;
            child=2*parent+1;
        }
    }

    public void push(int val) {
        if(isFull()) elem=Arrays.copyOf(elem,elem.length*2);
        elem[usedSize]=val;
        shiftUp(usedSize);
        usedSize++;
    }

    private void shiftUp(int child) {
        int parent=(child-1)/2;
        while(child>0){
            if(elem[child]<elem[parent]){
                break;
            }else{
                int tmp=elem[parent];
                elem[parent]=elem[child];
                elem[child]=tmp;
            }
            child=parent;
            parent=(child-1)/2;
        }
    }

    public boolean isFull() {
        return usedSize==elem.length;
    }

    public void pollHeap() {
        elem[0]=elem[usedSize-1];
        usedSize--;
        shiftDown(0,usedSize);
    }

    public boolean isEmpty() {
        return usedSize==0;
    }
    public int peekHeap() {
        return elem[0];
    }
}